import java.util.Deque;
import java.util.LinkedList;

/**
 * LeetCode 20. 有效的括号
 */
public class Solution_20 {
    /**
     * 栈
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public boolean isValid(String s) {
        if (s == null || s.length() < 2) {
            return false;
        }
        char[] charArray = s.toCharArray();
        Deque<Character> stack = new LinkedList<>();
        for (char c : charArray) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char topChar = stack.pop();
                if (c == ')' && topChar != '(') {
                    return false;
                } else if (c == ']' && topChar != '[') {
                    return false;
                } else if (c == '}' && topChar != '{') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}
